import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class J092601 {
    public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(){

         }
         TreeNode(int val){
             this.val = val;
         }
         TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
         }
    }
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode traversed = null;
        while(cur != null || !stack.isEmpty()){
            //遍历“左“节点
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //查看栈顶元素
            TreeNode top = stack.peek();
            //将该节点的右子树入栈，若该节点的右节点为已出栈或空元素，说明该节点的左右子树都已经处理完毕，下一步将该节点出栈。
            if(top.right != null && top.right != traversed){
                cur = top.right;
                continue;
            }
            list.add(stack.pop().val);
            //标记已出栈元素
            traversed = top;
        }
        return list;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right =  new TreeNode(2);
        root.right.left = new TreeNode(3);
        List<Integer> lastTree = postorderTraversal(root);
        System.out.println(lastTree.toString());
    }
}
